"""
题目：https://leetcode-cn.com/problems/unique-binary-search-trees/
    给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
    示例 1:
    输入：n = 3
    输出：5
思路：动态规划。假设G(x)表示使用x个节点时组成一个节点值从1到n互不相同的二叉搜索树。当x=0或者x=1时，G(x)=1，当x>=2时，G(x) = ∑ G(i−1)⋅G(n−i)
时间复杂度：O(n^2)
空间复杂度：O(n)
"""
class Solution:
    def numTrees(self, n: int) -> int:
        G = [0] * (n + 1)
        G[0],G[1] = 1,1
        for i in range(2,n + 1):
            for j in range(1,i + 1):
                G[i] += G[j - 1] * G[i - j]
        return G[n]